package q654_constructMaximumBinaryTree;

import CommonClass.Common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 此题的思路和利用中序和后序或者中序和前序构建二叉树几乎一致
 * 使用递归的方式即可
 * 只是构建的树性质不同
 */
public class Solution_1 {
    private Map<Integer, Integer> indexMap;
    int temp = 0;
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int n = nums.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<>();
        int maxNum = 0;
        for (int i = 0; i < n; i++) {
            indexMap.put(nums[i], i);
            maxNum = Math.max(maxNum, nums[i]);
        }
        return myBuildTree(nums, maxNum, 0, n - 1);
    }

    private TreeNode myBuildTree(int[] nums, int maxNum, int l, int r) {
        if (l > r) {
            return null;
        }
        TreeNode root = new TreeNode(maxNum);
        // 找出maxNum位置 可以确定maxNum左右节点的数量
        int root_index = indexMap.get(maxNum);

        temp = 0;
        for (int i = l; i < root_index; i++) {
            temp = Math.max(temp, nums[i]);
        }
        // 然后按照105 或者 106题思路即可
        root.left = myBuildTree(nums, temp, l, root_index - 1);

        temp = 0;
        for (int i = root_index + 1; i <= r; i++) {
            temp = Math.max(temp, nums[i]);
        }
        root.right = myBuildTree(nums, temp, root_index + 1, r);

        return root;
    }


}
